package leetcode.linked;

/**
 * 86. 分隔链表
 * <p>
 * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
 * <p>
 * 你应当保留两个分区中每个节点的初始相对位置。
 * <p>
 * 示例:
 * <p>
 * 输入: head = 1->4->3->2->5->2, x = 3
 * 输出: 1->2->2->4->3->5
 * 分析： 使用双链表拼接法，一个链表存放比v小的值 一个俩表存放比v大的值，
 * 时间复杂度 O(n) 空间复杂度 O(n)   当使用两个链表进行存放的时候，存放的是值，而不是引用。
 */
public class Solution86 {

    public static ListNode partition(ListNode head, int x) {
        //设立两个链表 都带有虚拟头结点
        ListNode lt = new ListNode(-1);
        ListNode gt = new ListNode(-1);
        ListNode gtHead = gt;
        ListNode ltHead = lt;
        //遍历head将元素进行分开。
        while (head != null) {
            ListNode node = new ListNode(head.val);
            if (head.val < x) {
                lt.next = node;
                lt = lt.next;
            } else {
                gt.next = node;
                gt = gt.next;
            }
            head = head.next;
        }


        //lt 指向最后一个元素
        lt.next = gtHead.next;
        return ltHead.next;
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 2, 5, 2};
        ListNode ls = new ListNode(arr);
        System.out.println(partition(ls, 3));
    }
}
